// standard headers
#include <istream>
#include <vector>
#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdlib>

// boost headers
#include <boost/format.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/filesystem/path.hpp>

// components headers
#include <tree.h>
#include <ultoa.h>
#include <perlutil.h>
#include <matrix.h>
#include <tree_ops.h>
#include <portable_timer.h>
#include <progress_indicator.h>
#include <print_error.h>
#include <index_string.h>
#define DEBUG_LEVEL 6
#include <debug_func.h>
#include <stdlib.h>






using boost::format;
using boost::lexical_cast;
using boost::filesystem::path;
using std::vector;
using std::ostringstream;

using std::string;
using std::fill;
using std::ofstream;
using std::cout;
using std::cin;
using std::cerr;
using std::ifstream;
using std::map;
using std::pair;
using std::istream;
using std::max;
using std::min;
using namespace bcpp_matrix;
using namespace bcpp_tree_ops;





struct do_assign_new_UIDs_from_leaf_up
{
	bcpp_tree::t_tree&						tree;
	vector<unsigned>							UIDs;
	unsigned									curr_UID;
	do_assign_new_UIDs_from_leaf_up(bcpp_tree::t_tree& tree_):
		tree(tree_), UIDs(tree_.get_node_count()), curr_UID(0)
	{
		// assign UIDs for leaves first
		for (unsigned i = 0, sz = tree.get_leaf_count(); i < sz; ++i)
			UIDs[tree.get_leaf(i).get_UID()] = curr_UID++;
		recurse(tree.get_root());
	}
	void recurse(bcpp_tree::t_node* node);

};

void do_assign_new_UIDs_from_leaf_up::recurse(bcpp_tree::t_node* node)
{
	if (node->is_leaf())
		return;
	for (unsigned i = 0; i < node->get_children_count(); ++i)
		recurse(node->get_child(i));
	UIDs[node->get_UID()] = curr_UID++;
}



//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	main

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

struct t_regex_to_species_UID
{

	string		regex;
	unsigned    UID;
	t_regex_to_species_UID(const string& r, unsigned UID_): regex(r), UID(UID_){}
};

void read_regex_to_species_UID(	std::istream&							strm,
								bcpp_tree::t_tree& 					species_tree,
								std::vector<t_regex_to_species_UID>&	regex_to_species)
{
	unsigned cnt_taxa = species_tree.get_leaf_count();


	// make sure tax names are unique
	t_index_string taxa_names_indexed;

	//
	// get a list of UIDs to correspond to the taxa names
	//
	vector<unsigned> species_UID;
	for (unsigned i = 0; i < cnt_taxa; ++i)
	{
		bool added;
		unsigned index = taxa_names_indexed.index(species_tree.get_leaf(i).get_name(), added);
		assert(index == i);
		if (!added)
			throw std::logic_error("Two species have the same name ["
									+ species_tree.get_leaf(i).get_name() + "]");
		species_UID.push_back(species_tree.get_leaf(i).get_UID());
	}


	//
	// for each regular expression, look up the field
	//
	// make sure tax names is not attached to more than one regex.
	t_index_string regex_taxa_names_indexed;

	string line;
	vector<string> fields;
	unsigned cnt_lines = 0;
	while (getline(strm, line))
	{
		// split line into two using tab
		++cnt_lines;
		if (line.empty())
			continue;

		perl_split (line, "\t", perlutil::eCOUNT_EMPTY, fields, 2);
		if (fields[0].empty() || fields[1].empty())
			throw std::logic_error("Ill-formed regular expression / species line # "
									+ ultoa(cnt_lines));

		// die if regular expression for this species already parsed
		bool added;
		regex_taxa_names_indexed.index(fields[0], added);
		if (!added)
			throw std::logic_error("There are two regular expressions for the same species  ["
									+ fields[0] + "]");


		// die if species not in tree
		unsigned index;
		if (!taxa_names_indexed.is_indexed(fields[0], index))
			throw std::logic_error( "The following taxon [" +
									fields[0] + "] specified with a regular expression is not in the species tree.");


		regex_to_species.push_back(t_regex_to_species_UID(fields[1], species_UID[index]));
	}
	if (regex_to_species.size() != species_UID.size())
		throw std::logic_error("Regular expression for some species are missing. ("
								+ ultoa(regex_to_species.size())
								+ " supplied; "
								+ ultoa(species_UID.size())
								+ " expected)");
}




int main (int argc, char *argv[])
{
	// we use cout to print progress so flush per call
//	cout.setf(std::ios_base::unitbuf);

	try
	{
	std::ios::sync_with_stdio(false);

	string tree_name;
	bcpp_tree::t_tree initial_species_tree;
	initial_species_tree.set_sort_by_names(true);
	try
	{
		read_tree_from_stream(cin, initial_species_tree, tree_name);
	}
	catch(std::exception& e)
	{
		std_print_error(string(e.what()) + "\nPlease supply a valid New Hampshire tree on the command line.\n");
		return 1;
	}

	//
	//	Normalise species tree so that leaves come first and UID of lower branches/leaf
	//		always have smaller UID than that of higher branches
	//
	bcpp_tree::t_tree species_tree;
	initial_species_tree.get_normalized_tree(species_tree);

	cerr << "\tCalculating branch lengths...\n";
	// calculate branch lengths
	bcpp_tree_ops::do_calculate_branch_lengths branch_lengths(species_tree);

	// set node type to none
	std::vector<eNODETYPE>	node_types(species_tree.get_node_count(), eNONE);


	// print
	op_print_tree_elaborate print_tree_elaborate
								(species_tree,
								cerr,
								branch_lengths.lengths_to_leaves,
								branch_lengths.lengths_to_root,
								node_types,
								3	// precision
								);
	print_tree_elaborate.print();


	t_species_tree_map species_map(species_tree);
	std::vector<t_regex_to_species_UID>	regex_to_species;
	read_regex_to_species_UID(	cin, species_tree, regex_to_species);

	// set labels to nodes
	op_set_labels_to_children_names do_set_labels(species_tree);
	vector<string> species_node_labels = species_tree.get_node_labels();



	//
	//	print out
	//
	//	but reverse everything for better legibility

	// use reverse indices
	vector<unsigned> indices;
	for (unsigned i = 0; i < species_map.cnt_duplications.size(); ++i)
		indices.push_back(i);
	std::reverse(indices.begin(),  indices.end());

	// labels in reverse
	std::reverse(species_node_labels.begin(),  species_node_labels.end());



	cerr << "\nParent lookup\n";
	t_dense_matrix<string> phylo_lookup_name(species_map.parent_species_UID.size());
	for (unsigned i = 0, sz = species_map.parent_species_UID.size(); i != sz; ++i)
		for (unsigned j = 0; j != sz; ++j)
			phylo_lookup_name[i][j] = species_tree.get_node_labels()[species_map.parent_species_UID[i][j]];
	t_dense_matrix<string> phylo_lookup_name_rev(phylo_lookup_name.size());
	phylo_lookup_name.sub_matrix(indices, phylo_lookup_name_rev);
	dump_to_stream(cerr,  phylo_lookup_name_rev, species_node_labels);


	cerr << "\nMapping function (Count missing taxa)\n";
	t_dense_matrix<unsigned> cnt_missing_taxa_rev(species_map.cnt_missing_taxa.size());
	species_map.cnt_missing_taxa.sub_matrix(indices, cnt_missing_taxa_rev);
	dump_to_stream(cerr,  cnt_missing_taxa_rev, species_node_labels);


	cerr << "\nMapping function (Count duplications)\n";
	t_dense_matrix<unsigned> cnt_duplications_rev(species_map.cnt_duplications.size());
	species_map.cnt_duplications.sub_matrix(indices, cnt_duplications_rev);
	dump_to_stream(cerr,  cnt_duplications_rev, species_node_labels);

	cerr << "\nRegular expressions\n";
	for (unsigned i = 0; i < regex_to_species.size(); ++i)
	{
		cerr
				<< species_tree.get_node_names()[regex_to_species[i].UID]
				<< "\t"
				<<  regex_to_species[i].regex << "\n";
	}

	cerr << "\n\tAll finished!!\n\n";

	return 0;
	}
	catch(std::exception& e)
	{
		std_print_error(string(e.what()));
		return 1;
	}
}




